#!/usr/bin/env/python3
# -*- coding: utf-8 -*-

"""
@Time    : 2020/3/12 20:24
@Author  : Chen Liu
@FileName: min_cost.py
@Software: PyCharm
"""


# 给定n个节点，一个列表里面保存着节点之间存在的边
# 问题1：给定一个图如何判断两个节点之间是否互通,即存在环？--输出True or False
# 思路：
# 1. 建立一个列表,保存与每个节点之间连接的其他节点
# 2. 对于每个节点, 对该节点进行深度优先遍历,判断该节点是否存在闭环.
# 3. 深度优先遍历每个节点:
#    3.1 预先给该节点设定一个值,如果该节点的下一个节点的值等于该值,则返回True
#    3.2 遍历该节点的所有下一个节点,并进行深度遍历.
#    3.3 如果该节点不存在闭环,则将该节点设为另一个值,返回False

def is_exisit(n, road):
    if not road:
        return True
    # 构建一个列表或者字典保存与每个节点存在路径的其他节点
    d = [[] for _ in range(n)]
    print(d)
    for r in road:
        a, b = r
        d[a-1].append(b)

    visited = [0] * n

    def dfs(i):
        # 递归终止条件
        if visited[i-1] == 1:
            return True

        if visited[i-1] == -1:
            return False
        # 预先令该节点的值为1.如果下一个节点的值等于1，则认为该图中存在环
        visited[i-1] = 1
        for next in d[i-1]:
            if dfs(next):
                return True
        # 如果不存在环，则令该节点为-1，不影响判断其他节点
        visited[i-1] = -1
        return False

    for i in range(n):
        if dfs(i):
            return True
    return False


# 问题2：如何计算任意两个节点之间的最短路径？
# 输出:所有节点之间的路径
# 参考网址: https://www.cnblogs.com/wangyuliang/p/9216365.html
# 弗洛伊德算法:
# 1. 输入初始的路径,如果不存在路径则用一个最大值代替
# 2. 三重循环是代码的核心

def min_road(n, road):
    inf = float('inf')
    dp = [[inf] * n for i in range(n)]
    for a, b in road:
        dp[a-1][b-1] = 1

    for i in range(n):
        dp[i][i] = 0

    print("dp: ", dp)

    # 三重循环是核心内容
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]

    for i in range(n):
        for j in range(n):
            if dp[i][j] == float('inf'):
                dp[i][j] = 0

    return dp


def min_cost():
    """
       计算建厂的最低成本
    """
    n, m, k = [int(x) for x in input().split()]
    cai_liao = [int(x) for x in input().split()]

    road = []
    for i in range(m):
        r = [int(x) for x in input().split()]
        road.append(r)

    all_cost = []
    d = [[] for _ in range(k)]
    for i, j in enumerate(cai_liao):
        d[j].append(i)

    # 计算所有节点之间的最短路径
    dp = min_road(n, road)
    for i in range(n):
        cost = 0
        for j in range(k):
            if j == cai_liao[i]:
                continue
            cost_list = []
            for m in d[j]:
                cost_list.append(dp[i][m])
            cost += min(cost_list)

        all_cost.append(cost)

    return all_cost


if __name__ == "__main__":
    n = 5
    road = [[1, 2], [2, 5], [3, 4], [4, 5], [3, 1], [5, 3]]
    res = is_exisit(n, road)
    print(res)

    dp_r = min_road(n, road)
    print("dp_r: ", dp_r)




